public class Order_0315 {
    /*
    给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。

     */
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    private int preIndex;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    private TreeNode buildTreeChild (int[] preorder, int[] inorder,int inBegin, int inEnd) {
        if (inBegin > inEnd) return null;
        TreeNode root = new TreeNode(preorder[preIndex]);
        int index = findIndex(inorder,inBegin,inEnd,preorder[preIndex]);
        if (index == -1) return null;
        preIndex++;
        root.left = buildTreeChild(preorder, inorder, inBegin, index - 1);
        root.right = buildTreeChild(preorder, inorder, index + 1, inEnd);
        return root;
    }
    private int findIndex (int[] inorder, int inBegin, int inEnd, int val) {
        for (int i = inBegin; i <= inEnd; i++) {
            if (inorder[i] == val) return i;
        }
        return -1;
    }
}
